#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;


// Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };
 
class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        func(root);
        this->index = 0;
        this->size = temp.size();
    }
    
    int next() {
        if(hasNext()){
            int value = temp[index];
            ++index;
            return value;
        }
    }
    
    bool hasNext() {
        if(index<size){
            return true;
        }
        return false;
    }
    void func(TreeNode* root){
        if(root==nullptr){
            return;
        }
        func(root->left);
        temp.push_back(root->val);
        func(root->right);
    }

public:
    vector<int> temp;
    int index = 0;
    int size = 0;
    
};


//不用递归实现一波
class BSTIterator {
public:
    BSTIterator(TreeNode* root) {
        this->root = root;
    }
    
    int next() {
        while(root!=nullptr){
            S.push(root);
            root = root->left;
        }
        TreeNode* temp = S.top();
        int value = temp->val;
        S.pop();
        root = temp->right;
        return value;
    }
    
    bool hasNext() {
        return !S.empty()||root!=nullptr;
    }
    
public:
    stack<TreeNode*> S;
    TreeNode* root;
};